package com.careercup.question.id17962663;

import java.util.ArrayDeque;
import java.util.Deque;

public class Solution {
	private static class Node<T> {
		Node<T> left, right;
		T value;
		public Node(T value) {
			this.value = value;
		}
		public void inorderPrint() {
			Node<T> cur = this;
	
			Deque<Node<T>> stack = new ArrayDeque<Node<T>>();
	
			while( cur != null ) {
				if( cur.left != null ) {
					stack.push(cur);
					cur = cur.left;
				}
				else {
					System.out.println( cur.value );
					cur = cur.right;
					while( cur == null && ! stack.isEmpty() ) {
						cur = stack.pop();
						System.out.println( cur.value );
						cur = cur.right;
					}
				}
			}
		}
	}
	/**
	 *               01
	 *       02              03
	 *   04      05      06      07
	 * 08  09  10  11  12  13  14  15
	 * @param args
	 */
	 public static void main(String[] args) {
		 Node<String> n1 = new Node<String>("1"), n2 = new Node<String>("2");
		 Node<String> n3 = new Node<String>("3"), n4 = new Node<String>("4");
		 Node<String> n5 = new Node<String>("5"), n6 = new Node<String>("6");
		 Node<String> n7 = new Node<String>("7"), n8 = new Node<String>("8");
		 Node<String> n9 = new Node<String>("9"), n10 = new Node<String>("10");
		 Node<String> n11 = new Node<String>("11"), n12 = new Node<String>("12");
		 Node<String> n13 = new Node<String>("13"), n14 = new Node<String>("14");
		 Node<String> n15 = new Node<String>("15");
		 n1.left = n2;
		 n1.right = n3;
		 n2.left = n4;
		 n2.right = n5;
		 n3.left = n6;
		 n3.right = n7;
		 n4.left = n8;
		 n4.right = n9;
		 n5.left = n10;
		 n5.right = n11;
		 n6.left = n12;
		 n6.right = n13;
		 n7.left = n14;
		 n7.right = n15;
		 n1.inorderPrint();
	 }
}
